# 定义结点
class Node(object):
    def __init__(self, item):
        self.item = item
        self.next = None
        self.prev = None


# 定义双向链表
class DoubleLinkList(object):
    def __init__(self):
        self._head = None

    # 判断是否为空链表
    def is_empty(self):
        # 没有头结点说明是空链表
        return self._head is None

    # 返回链表长度
    def get_length(self):
        temp = self._head
        length = 0
        while temp is not None:
            length += 1
            temp = temp.next
        return length

    # 遍历链表
    def travel(self):
        temp = self._head
        while temp is not None:
            print(temp.item)
            temp = temp.next
        print("")

    # 从头部添加
    def add(self, item):
        node = Node(item)
        # 如果是空链表, 添加的结点就是头结点
        if self.is_empty():
            self._head = node
        else:
            # 新节点后继指向老的头结点
            node.next = self._head
            # 老的头结点的前驱指向新节点
            self._head.prev = node
            # 变更头结点为新加入的结点
            self._head = node

    # 从尾部追加
    def append(self, item):
        node = Node(item)
        # 判断是否为空链表
        if self.is_empty():
            # 是空链表就把新结点当作头结点
            self._head = node
        else:
            temp = self._head
            # 遍历循环找到尾结点
            while temp.next is not None:
                temp = temp.next
            # 把尾结点的后继指向新结点
            temp.next = node
            # 把新结点的前驱指向尾结点
            node.prev = temp

    # 查找结点是否存在
    def exist(self, item):
        temp = self._head
        # 遍历链表, 找到值item的结点就返回True
        while temp is not None:
            if temp.item == item:
                return True
            temp = temp.next
        return False

    # 任意位置插入结点
    def insert(self, position, item):
        if position <= 0:
            self.add(item)
        elif position > (self.get_length() - 1):
            self.append(item)
        else:
            node = Node(item)
            temp = self._head
            count = 0
            # temp移动到指定位置的前一个位置
            while count < (position - 1):
                count += 1
                temp = temp.next
            # 把要插入的结点的prev指向temp
            node.prev = temp
            # 把要插入的结点的next指向temp的后一个结点
            node.next = temp.next
            # 把temp的后一个结点的prev指向要插入的结点
            temp.next.prev = node
            # 把temp的next指向要插入的结点
            temp.next = node

    # 删除结点
    def remove(self, item):
        if self.is_empty():
            return
        else:
            temp = self._head
            # 如果头结点就是要删除的结点
            if temp.item == item:
                if temp.next is None:
                    # 如果链表只有一个结点, 直接变成空链表
                    self._head = None
                else:
                    # 如果不止一个结点, 把第二个结点的prev指向None
                    temp.next.prev = None
                    # 第二个结点直接变成头结点
                    self._head = temp.next
                return
            # 头结点不是要删除的结点, 遍历链表
            while temp is not None:
                # 找到就删除
                if temp.item == item:
                    # 前驱结点的next指向后继结点
                    temp.prev.next = temp.next
                    # 后继结点的prev指向前驱结点
                    temp.next.prev = temp.prev
                    break
                # 没找到继续遍历
                temp = temp.next
